using System;
using System.Collections.Generic;

namespace Test.ConsoleProgram.Algorithm.Solution
{
    [TestDescription("算法: 0204. 计数质数")]
    public class No0204_CountPrimes : AbsBaseTestItem
    {
        /*
        统计所有小于非负整数 n 的质数的数量。
        示例 1：
            输入：n = 10
            输出：4
            解释：小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。
        示例 2：
            输入：n = 0
            输出：0
        示例 3：
            输入：n = 1
            输出：0
        提示：
            0 <= n <= 5 * 106
        */

        public override void OnTest()
        {
            OnTest(CountPrimes_Enum);
            OnTest(CountPrimes_EhrlichSieve);
            OnTest(CountPrimes_LineSieve);
        }
        private void OnTest(Func<int, int> method)
        {
            Assert.TestExe(method, 10, 4);
            Assert.TestExe(method, 0, 0);
            Assert.TestExe(method, 1, 0);
            Assert.TestExe(method, 3, 1);
        }

        /// <summary>
        /// 方法一：枚举
        /// </summary>
        public int CountPrimes_Enum(int n)
        {
            bool isPrimes(int num)
            {
                for (int i = 2; i < num; i++)
                    if (num % i == 0)
                        return false;
                return true;
            };
            int ans = 0;
            for (int i = 2; i < n; i++)
            {
                if (isPrimes(i))
                    ans++;
            }
            return ans;
        }

        /// <summary>
        /// 方法二：埃氏筛
        /// </summary>
        public int CountPrimes_EhrlichSieve(int n)
        {
            int[] isPrimes = new int[n];
            Array.Fill(isPrimes, 1);
            int ans = 0;
            for (int i = 2; i < n; i++)
            {
                if (isPrimes[i] != 1)
                    continue;
                ans++;
                if ((long)i * i >= n)
                    continue;
                for (int j = i * i; j < n; j += i)
                {
                    isPrimes[j] = 0;
                }
            }
            return ans;
        }

        /// <summary>
        /// 方法三：线性筛
        /// </summary>
        public int CountPrimes_LineSieve(int n)
        {
            List<int> primes = new List<int>();
            int[] isPrimes = new int[n];
            Array.Fill(isPrimes, 1);
            for (int i = 2; i < n; i++)
            {
                if (isPrimes[i] == 1)
                {
                    primes.Add(i);
                }
                for (int j = 0; j < primes.Count && i * primes[j] < n; j++)
                {
                    isPrimes[i * primes[j]] = 0;
                    if (i % primes[j] == 0)
                    {
                        break;
                    }
                }
            }
            return primes.Count;
        }
    }
}
